Find the distance value between two arrays [Binary Search, Two Pointers]¶
Time: O((N+M)xLogM); Space: O(1); easy
Given two integer arrays arr1 and arr2, and the integer d, return the distance value between the two arrays.
The distance value is defined as the number of elements arr1[i] such that there is not any element arr2[j] where |arr1[i]-arr2[j]| <= d.
Example 1:
Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
Output: 2
Explanation:
For arr1[0]=4 we have:
|4-10|=6 > d=2
|4-9|=5 > d=2
|4-1|=3 > d=2
|4-8|=4 > d=2
For arr1[1]=5 we have:
|5-10|=5 > d=2
|5-9|=4 > d=2
|5-1|=4 > d=2
|5-8|=3 > d=2
For arr1[2]=8 we have:
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2
Example 2:
Input: arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
Output: 2
Example 3:
Input: arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
Output: 1
Constraints:
1 <= len(arr1), len(arr2) <= 500
-10^3 <= arr1[i], arr2[j] <= 10^3
0 <= d <= 100
Hints:
Sort ‘arr2’ and use binary search to get the closest element for each ‘arr1[i]’, it gives a time complexity of O(NLogN).
1. Binary Search [O((N+M)*LogM), O(1)]¶
[1]:
import bisect
class Solution1(object):
"""
Time: O((N+M)*LogM)
Space: O(1)
"""
def findTheDistanceValue(self, arr1, arr2, d):
"""
:type arr1: List[int]
:type arr2: List[int]
:type d: int
:rtype: int
"""
arr2.sort()
result, i, j = 0, 0, 0
for x in arr1:
j = bisect.bisect_left(arr2, x)
left = arr2[j-1] if j-1 >= 0 else float("-inf")
right = arr2[j] if j < len(arr2) else float("inf")
result += left+d < x < right-d
return result
[2]:
s = Solution1()
arr1 = [4,5,8]
arr2 = [10,9,1,8]
d = 2
assert s.findTheDistanceValue(arr1, arr2, d) == 2
arr1 = [1,4,2,3]
arr2 = [-4,-3,6,10,20,30]
d = 3
assert s.findTheDistanceValue(arr1, arr2, d) == 2
arr1 = [2,1,100,3]
arr2 = [-5,-2,10,-3,7]
d = 6
assert s.findTheDistanceValue(arr1, arr2, d) == 1
2. Two Pointers [O(NLogN + MLogM), O(1)]¶
[3]:
class Solution2(object):
"""
Time: O(NLogN + MLogM)
Space: O(1)
"""
def findTheDistanceValue(self, arr1, arr2, d):
"""
:type arr1: List[int]
:type arr2: List[int]
:type d: int
:rtype: int
"""
arr1.sort(), arr2.sort()
result, i, j = 0, 0, 0
while i < len(arr1) and j < len(arr2):
if arr1[i]-arr2[j] > d:
j += 1
continue
result += arr2[j]-arr1[i] > d
i += 1
return result+len(arr1)-i
[4]:
s = Solution2()
arr1 = [4,5,8]
arr2 = [10,9,1,8]
d = 2
assert s.findTheDistanceValue(arr1, arr2, d) == 2
arr1 = [1,4,2,3]
arr2 = [-4,-3,6,10,20,30]
d = 3
assert s.findTheDistanceValue(arr1, arr2, d) == 2
arr1 = [2,1,100,3]
arr2 = [-5,-2,10,-3,7]
d = 6
assert s.findTheDistanceValue(arr1, arr2, d) == 1